package com.lee.algorithm.linkedlist;

import com.lee.algorithm.linkedlist.struct.OneWayNode;

import java.util.Stack;

/***
 * @description: 回文链表
 *      判断一个单项链表是否是回文链表
 * @author : 博客园 @ 青石路
 * @date: 2021/11/29 21:42
 */
public class PalindromeList {

    public static void main(String[] args) {
        OneWayNode<String> head = new OneWayNode<String>("head");
        OneWayNode<String> n1 = new OneWayNode<String>("h2");
        OneWayNode<String> n2 = new OneWayNode<String>("h1");
        OneWayNode<String> n3 = new OneWayNode<String>("h2");
        OneWayNode<String> n4 = new OneWayNode<String>("head");

        head.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        // boolean b = judgePalindrome(head);

        // boolean b = judgePalindrome2(head);

        boolean b = isPalindrome(head);
        System.out.println(b);
    }



    /**
     * 所有元素全部入栈，然后从头至尾遍历链表的同时进行出栈比较
     *
     * @author 博客园 @ 青石路
     * @param head
     * @return
     */
    public static boolean judgePalindrome(OneWayNode<String> head) {

        if(head == null) {
            return false;
        }

        Stack<OneWayNode<String>> stack = new Stack<>();
        OneWayNode<String> cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        cur = head;
        while(cur != null) {
            OneWayNode<String> pop = stack.pop();
            if (!cur.value.equals(pop.value)) {
                return false;
            }
            cur = cur.next;
        }

        return true;
    }

    /**
     * 快慢指针 + 栈，对称轴右侧的元素进行入栈
     *      慢指针一次移动一个，快指针一次移动两个，当快指针走完的时候，慢指针来到中点的位置
     *      慢指针之后的元素放入栈中
     *
     * @author 博客园 @ 青石路
     * @param head
     * @return
     */
    public static boolean judgePalindrome2(OneWayNode<String> head) {

        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }

        OneWayNode<String> slow = head;
        OneWayNode<String> fast = head;
        Stack<OneWayNode<String>> stack = new Stack<>();
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 链表右侧元素入栈
        while (slow != null) {
            stack.push(slow);
            slow = slow.next;
        }

        fast = head;
        while (!stack.isEmpty()) {
            slow = stack.pop();
            if (!slow.value.equals(fast.value)) {
                return false;
            }
            fast = fast.next;
        }

        return true;
    }

    /**
     * 快慢指针，快指针走完的时候，慢指针所在的元素的 next = null，慢指针后的元素进行逆序
     * 得到两个单项链表，从头至尾逐个比较
     * （右侧记得还原到原链表中）
     *
     * @author 博客园 @ 青石路
     * @param head
     * @return
     */
    public static boolean judgePalindromePlus(OneWayNode<String> head) {

        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }

        OneWayNode<String> slow = head;
        OneWayNode<String> fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // slow 及之后的链表元素进行反转
        OneWayNode<String> cur = slow;
        slow = null;
        while (cur != null) {
            fast = cur.next;
            cur.next = slow;
            slow = cur;
            cur = fast;
        }

        // 逆序完后，slow 是逆序后的头节点
        // 回文判断
        fast = head;
        cur = slow;
        boolean isPalindrome = true;
        while (cur != null) {
            if (!cur.value.equals(fast.value)) {
                isPalindrome = false;
                break;
            }
            cur = cur.next;
            fast = fast.next;
        }

        // 将反转的链表还原到原链表中
        cur = slow;
        slow = null;
        while (cur != null) {
            fast = cur.next;
            cur.next = slow;
            slow = cur;
            cur = fast;
        }

        return isPalindrome;
    }

    public static void print(OneWayNode<String> head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }

    /**
     * 1、拷贝原链表，并对拷贝后的链表进行反转
     * 2、新旧链表对应位置逐一比较
     *
     * @author 博客园 @ 青石路
     * @param head
     * @return
     */
    public static boolean isPalindrome(OneWayNode<String> head) {
        if (head == null) {
            return false;
        }

        OneWayNode cur = head;
        OneWayNode pre = null;
        while (cur != null) {
            OneWayNode node = new OneWayNode(cur.value);
            node.next = pre;
            pre = node;
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            if (!cur.value.equals(pre.value)) {
                return false;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return true;
    }
}
